#ifndef __BWLIB_NUMBER_THEORY_CONGRUENCE_EQUATION_H__
#define __BWLIB_NUMBER_THEORY_CONGRUENCE_EQUATION_H__
#include "../config.h"
#include "gcd.h"
#include "module.h"

namespace bwlib
{
	/* @brief: 求解 ax = b (mod p)
	   @complexity: O(log n)
	   @param: a, b, p
	   @return: 最小的正整数解，不存在返回 -1 
	   @warning: integer overflow */
	template<typename Type>
	inline Type linear_congruence_equation(
		const Type& a, const Type& b, const Type& p)
	{
		Type x, k;
		Type g = exgcd(a, p, x, k);
		if(b % g != 0)
			return Type(-1);
		Type r = b / g;
		return mod_mul(x, r, p);
	}

	/* @brief: 求解 a^x = b (mod p)
	   @complexity: O(sqrt(n) * logn)
	   @param: a, b, p
	   @return: 最小的正整数解，不存在返回 -1 */
	// NOTE: Not implement
	template<typename Type>
	inline Type baga_step_giant_step(
		Type& a, Type& b, Type& p);
}

#endif
